import java.awt.image.renderable.RenderableImage;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-11-25
 * Time: 14:49
 */
public class Test3 {
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right) return;
        if(right - left + 1 < 5) {
            selectSort(array);
        }
        int midIndex = findIndex(left,right);
        swap(array,left,midIndex);
        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static int findIndex(int left, int right) {
        int mid = left + (right -left) >> 1;
        if(left < right) {
            if(mid < left) {
                return left;
            }else if(mid > right) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(mid < right) {
                return right;
            }else if (mid > left) {
                return left;
            }else {
                return mid;
            }
        }
    }

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while(left < right) {
            while(left < right && array[right] >=  tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    public static void radixSort(int[] array) {
        int[][] bucket = new int[10][array.length];
        int[] bucketElementCount = new int[10];
        int MAX = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > MAX) {
                MAX = array[i];
            }
        }
        int MAXCount = (MAX +"").length();
        for (int i = 0; i < MAXCount; i++) {
            for (int j = 0; j < array.length; j++) {
                int val = (array[j] /(int)(Math.pow(10,i))) % 10;
                bucket[val][bucketElementCount[val]] = array[j];
                bucketElementCount[val]++;
            }
        }
        int index = 0;
        for (int i = 0; i < bucketElementCount.length; i++) {
            if(bucketElementCount[i] != 0) {
                for (int j = 0; j < bucketElementCount[i]; j++) {
                    array[index++] = bucket[i][j];
                }
            }
            bucketElementCount[i] = 0;
        }
    }
    public static void main(String[] args) {
        int[] array = {4,6,2,6,0,2,3,8,9,2,4,8,2,2,7,9};
        //quickSort(array);
        radixSort(array);
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
    public static int getPos(int[] array, int n, int val) {
        // write code here
        int left = 0;
        int right = n - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(array[mid] > val) {
                right = mid - 1;
            }else if(array[mid] < val) {
                left = mid + 1;
            }else {
                if(mid == left || array[mid-1] != val) {
                    return mid;
                }else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main0(String[] args) {
        int[] array = {11,27,28,33};
        int ret = getPos(array,4,28);
        System.out.println(ret);
    }
}
